package com.company.ljh.medium;

import java.util.*;

/**
 * @description:
 * @projectName:leet_code
 * @see:com.company.ljh.medium
 * @author:ljh
 * @createTime:2023/7/6 11:07
 * @version:1.0
 */
public class 重新规划路线 {
    public static void main(String[] args) {
        int[][]connections = new int[][]{{0,1},{1,3},{2,3},{4,0},{4,5}};
        int n = 6;
        minReorder(6,connections);
    }
    //广度优先遍历，需要保存到当前节点的所有相连节点，并保存方向，由于二维矩阵创建会超时，因此使用ArrayList数组保存，同时需要保存反向边信息方便查找
    public static int minReorder(int n, int[][] connections) {
        //广度优先遍历
        Queue <Integer>queue = new LinkedList();
        //使用ArrayList数组来实现连接矩阵
        ArrayList<Integer>[]  isConnected= new ArrayList[n];
        //保存反向连接矩阵
        ArrayList<Integer>[]  otherisConnected= new ArrayList[n];

        for(int i =0 ;i< n;i++){
            isConnected[i] = new ArrayList();
            otherisConnected[i] = new ArrayList();
        }
        for(int i =0;i<connections.length;i++){
            isConnected[connections[i][0]].add(connections[i][1]);
            otherisConnected[connections[i][1]].add(connections[i][0]);
        }
        //保存翻转次数
        int result = 0;
        //标记是否访问
        boolean isVisited[] = new boolean[n];
        queue.offer(0);
        while(!queue.isEmpty()){
            int thisNode = queue.poll();
            isVisited[thisNode] = true;
            for(int next : isConnected[thisNode]){
                //正向边，需要翻转
                if(next == thisNode || isVisited[next])
                    continue;
                result++;
                queue.offer(next);
            }
            for(int next : otherisConnected[thisNode]){
                //反向边，不需要翻转
                if(next == thisNode || isVisited[next])
                    continue;
                queue.offer(next);
            }

        }
        return result;
    }
}
